package com.cwj;

public class Fenwick {

    int n;

    int[] tree;

    public Fenwick(int n) {
        this.n = n;
        this.tree = new int[n];
    }

    @Deprecated
    public int lowbit(int x) {
        return x & (-x);
    }


    /**
     * 将i位置加上k
     */
    public void update(int i, int k) {
        while (i < n) {
            tree[i] += k;
            i = i | (i + 1);
        }
    }

    public long sumRange(int i) {
        long res = 0;
        while (i >= 0) {
            res += tree[i];
            i = (i & (i + 1)) - 1;
        }
        return res;
    }

    public long sumRange(int l, int r) {
        return l == 0 ? sumRange(r) : sumRange(r) - sumRange(l - 1);
    }


}